Investigating Second Eigenvalue

  if (require("PageRank")) {
      library(PageRank)
    }else{
      devtools::install_github("ryangreenup/PageRank")
      library(PageRank)
    }

  library(pacman)
  pacman::p_load(PageRank, devtools, Matrix, igraph, mise, tidyverse, rgl, latex2exp)
#  mise()

Looking at Density

Constants

Define some constants

m    <- seq(from = 1, to = 10, length.out = 5)
m <- 5
beta <- seq(from = 1, to = 20, length.out = 10)
sz <- seq(from = 10, to = 1000, length.out = 10)
input_var <- expand.grid("m" = m, "beta" = beta, "size" = sz)
input_var

Function to Build Graph

random_graph <- function(m, beta, size) {
      g1 <- igraph::sample_pa(n = size, power = 3, m = m)
      A <- igraph::get.adjacency(g1) # Row to column
      A <- Matrix::t(A)

      A_dens <- mean(A)
      T      <- PageRank::power_walk_prob_trans(A, beta = beta)
      tr     <- sum(diag(T))
      e2     <- eigen(T, only.values = TRUE)$values[2] # R orders by descending magnitude
      return(c(abs(e2), mean(A), tr))
}

Return results

Map the function

rm(Y, data)
nc <- length(random_graph(1, 1, 1))
Y <- matrix(ncol = nc, nrow = nrow(input_var))
for (i in 1:nrow(input_var)) {
  X <- as.vector(input_var[i,])
  Y[i,] <-  random_graph(X$m, X$beta, X$size)
  print(i/nrow(input_var))
}
[1] 0.01
[1] 0.02
[1] 0.03
[1] 0.04
[1] 0.05
[1] 0.06
[1] 0.07
[1] 0.08
[1] 0.09
[1] 0.1
[1] 0.11
[1] 0.12
[1] 0.13
[1] 0.14
[1] 0.15
[1] 0.16
[1] 0.17
[1] 0.18
[1] 0.19
[1] 0.2
[1] 0.21
[1] 0.22
[1] 0.23
[1] 0.24
[1] 0.25
[1] 0.26
[1] 0.27
[1] 0.28
[1] 0.29
[1] 0.3
[1] 0.31
[1] 0.32
[1] 0.33
[1] 0.34
[1] 0.35
[1] 0.36
[1] 0.37
[1] 0.38
[1] 0.39
[1] 0.4
[1] 0.41
[1] 0.42
[1] 0.43
[1] 0.44
[1] 0.45
[1] 0.46
[1] 0.47
[1] 0.48
[1] 0.49
[1] 0.5
[1] 0.51
[1] 0.52
[1] 0.53
[1] 0.54
[1] 0.55
[1] 0.56
[1] 0.57
[1] 0.58
[1] 0.59
[1] 0.6
[1] 0.61
[1] 0.62
[1] 0.63
[1] 0.64
[1] 0.65
[1] 0.66
[1] 0.67
[1] 0.68
[1] 0.69
[1] 0.7
[1] 0.71
[1] 0.72
[1] 0.73
[1] 0.74
[1] 0.75
[1] 0.76
[1] 0.77
[1] 0.78
[1] 0.79
[1] 0.8
[1] 0.81
[1] 0.82
[1] 0.83
[1] 0.84
[1] 0.85
[1] 0.86
[1] 0.87
[1] 0.88
[1] 0.89
[1] 0.9
[1] 0.91
[1] 0.92
[1] 0.93
[1] 0.94
[1] 0.95
[1] 0.96
[1] 0.97
[1] 0.98
[1] 0.99
[1] 1
if (sum(abs(Y) != abs(Re(Y))) == 0) {
  Y <- Re(Y)
}
nrow(input_var)
[1] 100
nrow(Y)
[1] 100
Y <- as.data.frame(Y); colnames(Y) <- c("eigenvalue2", "A_dens", "trace")
(data <- cbind(input_var, Y)) %>% head()

Plot Results

pairs(data)

cor(data)
the standard deviation is zero
             m          beta          size eigenvalue2
m            1            NA            NA          NA
beta        NA  1.000000e+00  4.635990e-21   0.3091320
size        NA  4.635990e-21  1.000000e+00  -0.6207504
eigenvalue2 NA  3.091320e-01 -6.207504e-01   1.0000000
A_dens      NA -2.642753e-21 -5.916467e-01   0.8649706
trace       NA -3.880604e-01  6.586858e-01  -0.9874588
                   A_dens      trace
m                      NA         NA
beta        -2.642753e-21 -0.3880604
size        -5.916467e-01  0.6586858
eigenvalue2  8.649706e-01 -0.9874588
A_dens       1.000000e+00 -0.8183481
trace       -8.183481e-01  1.0000000
library(corrplot)
cormat = cor(data, method = 'spearman')
the standard deviation is zero
corrplot(cormat, method = "ellipse", type = "lower")

names(data)
[1] "m"           "beta"        "size"        "eigenvalue2"
[5] "A_dens"      "trace"      

Let’s look at a 3d Output

fig
Error: Tibble columns must have compatible sizes.
* Size 40: Column `x`.
* Size 100: Columns `y` and `z`.
ℹ Only values of size one are recycled.

names(data)
[1] "m"           "beta"        "size"        "eigenvalue2"
[5] "A_dens"      "trace"      
library(plotly)

# d <- data[sample(1:nrow(data), 1000),]
d <- data

fig <- plot_ly(d, x = ~A_dens, y = ~trace, z = ~eigenvalue2)
fig <- fig %>% add_markers(size = 1)
fig <- fig %>% layout(scene = list(xaxis = list(title = 'Density'),
                     yaxis = list(title = 'trace'),
                     zaxis = list(title = 'E2')))

fig

NA

Clearly I should be able to model this.

Let’s look at density, it’s continuous so I should be able to take splices of A_dens.

A_dens is dependent on p, so I’ll just use different ps

m    <- seq(from = 1, to = 9, length.out = 2)
beta <- seq(from = 1, to = 6, length.out = 10)
sz <- seq(from = 100, to = 1000, length.out = 4) %>% rev() # Big numbers first 

input_var <- expand.grid("m" = m, "beta" = beta, "size" = sz)
input_var


rm(Y, data)
nc <- length(random_graph(1, 1, 1))
Y <- matrix(ncol = nc, nrow = nrow(input_var))
for (i in 1:nrow(input_var)) {
  X <- as.vector(input_var[i,])
  Y[i,] <-  random_graph(X$m, X$beta, X$size)
  print(i/nrow(input_var))
}
[1] 0.0125
[1] 0.025
[1] 0.0375
[1] 0.05
[1] 0.0625
[1] 0.075
[1] 0.0875
[1] 0.1
[1] 0.1125
[1] 0.125
[1] 0.1375
[1] 0.15
[1] 0.1625
[1] 0.175
[1] 0.1875
[1] 0.2
[1] 0.2125
[1] 0.225
[1] 0.2375
[1] 0.25
[1] 0.2625
[1] 0.275
[1] 0.2875
[1] 0.3
[1] 0.3125
[1] 0.325
[1] 0.3375
[1] 0.35
[1] 0.3625
[1] 0.375
[1] 0.3875
[1] 0.4
[1] 0.4125
[1] 0.425
[1] 0.4375
[1] 0.45
[1] 0.4625
[1] 0.475
[1] 0.4875
[1] 0.5
[1] 0.5125
[1] 0.525
[1] 0.5375
[1] 0.55
[1] 0.5625
[1] 0.575
[1] 0.5875
[1] 0.6
[1] 0.6125
[1] 0.625
[1] 0.6375
[1] 0.65
[1] 0.6625
[1] 0.675
[1] 0.6875
[1] 0.7
[1] 0.7125
[1] 0.725
[1] 0.7375
[1] 0.75
[1] 0.7625
[1] 0.775
[1] 0.7875
[1] 0.8
[1] 0.8125
[1] 0.825
[1] 0.8375
[1] 0.85
[1] 0.8625
[1] 0.875
[1] 0.8875
[1] 0.9
[1] 0.9125
[1] 0.925
[1] 0.9375
[1] 0.95
[1] 0.9625
[1] 0.975
[1] 0.9875
[1] 1
if (sum(abs(Y) != abs(Re(Y))) == 0) {
  Y <- Re(Y)
}
nrow(input_var)
[1] 80
nrow(Y)
[1] 80
Y <- as.data.frame(Y); colnames(Y) <- c("eigenvalue2", "A_dens", "trace")
(data2 <- cbind(input_var, Y)) %>% head()
# save(data2, file = "/home/ryan/Sync/Studies/2020Spring/DiscProj/data2_ba.rdata")
# load(file = "/home/ryan/Sync/Studies/2020Spring/DiscProj/data2_ba.rdata")
data2$p <- (data2$m/data2$size)
names(data2)
[1] "m"           "beta"        "size"        "eigenvalue2"
[5] "A_dens"      "trace"       "p"          
ggplot(data2, mapping = aes(col = factor(p), x = beta, y = eigenvalue2)) +
  geom_point(size = 0.5) +
  stat_smooth(method = 'lm') +
  scale_size_continuous(range = c(0.1,1)) +
  labs(x = "Beta", y = TeX("Second Eigenvalue"), title = TeX("Second Eigenvalue given Matrix Density") ) +
  guides(col = guide_legend("Link Density (by m/n)"))  +
  theme_bw()

It appears that m/n=density is its own feature, it does not affect E2 linearly so lets hold beta constant and see how it affects E2.

If for instance m/n increases, say quadratically for a constant beta, then I should try and fit a linear model to (m/n)^2*beta

So what about when I very m, i.e. lets map that to colour now:

Even though it’s hard to capture the behaviour of m/n, the size of the graph and the average outdegree are going to be constants and so this relationship should persist for graphs where m<<n.

actually if they are all linearly related, maybe I could use a multiple linear regression?

Clearly non-normal residuals but +-5% is pretty good for a very complicated result.

I think I already looked at this but this again shows the relly clear, near linear relationship.

Obviously we can’t know m, but, we can know the average out degree, so let’s, take a graph, measure the average out degree, use our model, measure it’s performance.

LS0tCnRpdGxlOiAiSW52ZXN0aWdhdGluZyBTZWNvbmQgRWlnZW52YWx1ZSIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyBJbnZlc3RpZ2F0aW5nIFNlY29uZCBFaWdlbnZhbHVlCgpgYGB7cn0KICBpZiAocmVxdWlyZSgiUGFnZVJhbmsiKSkgewogICAgICBsaWJyYXJ5KFBhZ2VSYW5rKQogICAgfWVsc2V7CiAgICAgIGRldnRvb2xzOjppbnN0YWxsX2dpdGh1YigicnlhbmdyZWVudXAvUGFnZVJhbmsiKQogICAgICBsaWJyYXJ5KFBhZ2VSYW5rKQogICAgfQoKICBsaWJyYXJ5KHBhY21hbikKICBwYWNtYW46OnBfbG9hZChQYWdlUmFuaywgZGV2dG9vbHMsIE1hdHJpeCwgaWdyYXBoLCBtaXNlLCB0aWR5dmVyc2UsIHJnbCwgbGF0ZXgyZXhwKQojICBtaXNlKCkKYGBgCgoKCiMjIExvb2tpbmcgYXQgRGVuc2l0eQoKIyMjIENvbnN0YW50cwoKRGVmaW5lIHNvbWUgY29uc3RhbnRzCgpgYGB7cn0KbSAgICA8LSBzZXEoZnJvbSA9IDEsIHRvID0gMTAsIGxlbmd0aC5vdXQgPSA1KQptIDwtIDUKYmV0YSA8LSBzZXEoZnJvbSA9IDEsIHRvID0gMjAsIGxlbmd0aC5vdXQgPSAxMCkKc3ogPC0gc2VxKGZyb20gPSAxMCwgdG8gPSAxMDAwLCBsZW5ndGgub3V0ID0gMTApCmlucHV0X3ZhciA8LSBleHBhbmQuZ3JpZCgibSIgPSBtLCAiYmV0YSIgPSBiZXRhLCAic2l6ZSIgPSBzeikKaW5wdXRfdmFyCmBgYAoKIyMjIEZ1bmN0aW9uIHRvIEJ1aWxkIEdyYXBoCgpgYGB7cn0KcmFuZG9tX2dyYXBoIDwtIGZ1bmN0aW9uKG0sIGJldGEsIHNpemUpIHsKICAgICAgZzEgPC0gaWdyYXBoOjpzYW1wbGVfcGEobiA9IHNpemUsIHBvd2VyID0gMywgbSA9IG0pCiAgICAgIEEgPC0gaWdyYXBoOjpnZXQuYWRqYWNlbmN5KGcxKSAjIFJvdyB0byBjb2x1bW4KICAgICAgQSA8LSBNYXRyaXg6OnQoQSkKCiAgICAgIEFfZGVucyA8LSBtZWFuKEEpCiAgICAgIFQgICAgICA8LSBQYWdlUmFuazo6cG93ZXJfd2Fsa19wcm9iX3RyYW5zKEEsIGJldGEgPSBiZXRhKQogICAgICB0ciAgICAgPC0gc3VtKGRpYWcoVCkpCiAgICAgIGUyICAgICA8LSBlaWdlbihULCBvbmx5LnZhbHVlcyA9IFRSVUUpJHZhbHVlc1syXSAjIFIgb3JkZXJzIGJ5IGRlc2NlbmRpbmcgbWFnbml0dWRlCiAgICAgIHJldHVybihjKGFicyhlMiksIG1lYW4oQSksIHRyKSkKfQpgYGAKCiMjIyBSZXR1cm4gcmVzdWx0cwoKTWFwIHRoZSBmdW5jdGlvbgoKYGBge3J9CnJtKFksIGRhdGEpCm5jIDwtIGxlbmd0aChyYW5kb21fZ3JhcGgoMSwgMSwgMSkpClkgPC0gbWF0cml4KG5jb2wgPSBuYywgbnJvdyA9IG5yb3coaW5wdXRfdmFyKSkKZm9yIChpIGluIDE6bnJvdyhpbnB1dF92YXIpKSB7CiAgWCA8LSBhcy52ZWN0b3IoaW5wdXRfdmFyW2ksXSkKICBZW2ksXSA8LSAgcmFuZG9tX2dyYXBoKFgkbSwgWCRiZXRhLCBYJHNpemUpCiAgcHJpbnQoaS9ucm93KGlucHV0X3ZhcikpCn0KaWYgKHN1bShhYnMoWSkgIT0gYWJzKFJlKFkpKSkgPT0gMCkgewogIFkgPC0gUmUoWSkKfQpucm93KGlucHV0X3ZhcikKbnJvdyhZKQpZIDwtIGFzLmRhdGEuZnJhbWUoWSk7IGNvbG5hbWVzKFkpIDwtIGMoImVpZ2VudmFsdWUyIiwgIkFfZGVucyIsICJ0cmFjZSIpCihkYXRhIDwtIGNiaW5kKGlucHV0X3ZhciwgWSkpICU+JSBoZWFkKCkKYGBgCgoKIyMjIFBsb3QgUmVzdWx0cwoKCmBgYHtyfQpwYWlycyhkYXRhKQpjb3IoZGF0YSkKbGlicmFyeShjb3JycGxvdCkKY29ybWF0ID0gY29yKGRhdGEsIG1ldGhvZCA9ICdzcGVhcm1hbicpCmNvcnJwbG90KGNvcm1hdCwgbWV0aG9kID0gImVsbGlwc2UiLCB0eXBlID0gImxvd2VyIikKbmFtZXMoZGF0YSkKYGBgCkxldCdzIGxvb2sgYXQgYSAzZCBPdXRwdXQKCmBgYHtyfQpuYW1lcyhkYXRhKQpsaWJyYXJ5KHBsb3RseSkKCiBkIDwtIGRhdGFbc2FtcGxlKDE6bnJvdyhkYXRhKSwgMTAwKSxdCiBkIDwtIGRhdGEKCmZpZyA8LSBwbG90X2x5KGQsIHggPSB+cCwgeSA9IH5iZXRhLCB6ID0gfmVpZ2VudmFsdWUyKQpmaWcgPC0gZmlnICU+JSBhZGRfbWFya2VycyhzaXplID0gMSkKZmlnIDwtIGZpZyAlPiUgbGF5b3V0KHNjZW5lID0gbGlzdCh4YXhpcyA9IGxpc3QodGl0bGUgPSAnc2l6ZScpLAogICAgICAgICAgICAgICAgICAgICB5YXhpcyA9IGxpc3QodGl0bGUgPSAnQmV0YScpLAogICAgICAgICAgICAgICAgICAgICB6YXhpcyA9IGxpc3QodGl0bGUgPSAnRTInKSkpCgpmaWcKCmBgYAoKYGBge3J9CgpuYW1lcyhkYXRhKQpsaWJyYXJ5KHBsb3RseSkKCiMgZCA8LSBkYXRhW3NhbXBsZSgxOm5yb3coZGF0YSksIDEwMDApLF0KZCA8LSBkYXRhCgpmaWcgPC0gcGxvdF9seShkLCB4ID0gfkFfZGVucywgeSA9IH50cmFjZSwgeiA9IH5laWdlbnZhbHVlMikKZmlnIDwtIGZpZyAlPiUgYWRkX21hcmtlcnMoc2l6ZSA9IDEpCmZpZyA8LSBmaWcgJT4lIGxheW91dChzY2VuZSA9IGxpc3QoeGF4aXMgPSBsaXN0KHRpdGxlID0gJ0RlbnNpdHknKSwKICAgICAgICAgICAgICAgICAgICAgeWF4aXMgPSBsaXN0KHRpdGxlID0gJ3RyYWNlJyksCiAgICAgICAgICAgICAgICAgICAgIHpheGlzID0gbGlzdCh0aXRsZSA9ICdFMicpKSkKCmZpZwoKYGBgCgoKQ2xlYXJseSBJIHNob3VsZCBiZSBhYmxlIHRvIG1vZGVsIHRoaXMuCgpMZXQncyBsb29rIGF0IGRlbnNpdHksIGl0J3MgY29udGludW91cyBzbyBJIHNob3VsZCBiZSBhYmxlIHRvICB0YWtlIHNwbGljZXMgb2YgQV9kZW5zLgoKQV9kZW5zIGlzIGRlcGVuZGVudCBvbiBwLCBzbyBJJ2xsIGp1c3QgdXNlIGRpZmZlcmVudCBwcwoKCmBgYHtyfQptICAgIDwtIHNlcShmcm9tID0gMSwgdG8gPSA5LCBsZW5ndGgub3V0ID0gMykKYmV0YSA8LSBzZXEoZnJvbSA9IDEsIHRvID0gNiwgbGVuZ3RoLm91dCA9IDEwMCkKc3ogPC0gc2VxKGZyb20gPSAxMDAsIHRvID0gMTAwMCwgbGVuZ3RoLm91dCA9IDMpICU+JSByZXYoKSAjIEJpZyBudW1iZXJzIGZpcnN0IAoKaW5wdXRfdmFyIDwtIGV4cGFuZC5ncmlkKCJtIiA9IG0sICJiZXRhIiA9IGJldGEsICJzaXplIiA9IHN6KQppbnB1dF92YXIKCgpybShZLCBkYXRhKQpuYyA8LSBsZW5ndGgocmFuZG9tX2dyYXBoKDEsIDEsIDEpKQpZIDwtIG1hdHJpeChuY29sID0gbmMsIG5yb3cgPSBucm93KGlucHV0X3ZhcikpCmZvciAoaSBpbiAxOm5yb3coaW5wdXRfdmFyKSkgewogIFggPC0gYXMudmVjdG9yKGlucHV0X3ZhcltpLF0pCiAgWVtpLF0gPC0gIHJhbmRvbV9ncmFwaChYJG0sIFgkYmV0YSwgWCRzaXplKQogIHByaW50KGkvbnJvdyhpbnB1dF92YXIpKQp9CmlmIChzdW0oYWJzKFkpICE9IGFicyhSZShZKSkpID09IDApIHsKICBZIDwtIFJlKFkpCn0KbnJvdyhpbnB1dF92YXIpCm5yb3coWSkKWSA8LSBhcy5kYXRhLmZyYW1lKFkpOyBjb2xuYW1lcyhZKSA8LSBjKCJlaWdlbnZhbHVlMiIsICJBX2RlbnMiLCAidHJhY2UiKQooZGF0YTIgPC0gY2JpbmQoaW5wdXRfdmFyLCBZKSkgJT4lIGhlYWQoKQojIHNhdmUoZGF0YTIsIGZpbGUgPSAiL2hvbWUvcnlhbi9TeW5jL1N0dWRpZXMvMjAyMFNwcmluZy9EaXNjUHJvai9kYXRhMl9iYS5yZGF0YSIpCiMgbG9hZChmaWxlID0gIi9ob21lL3J5YW4vU3luYy9TdHVkaWVzLzIwMjBTcHJpbmcvRGlzY1Byb2ovZGF0YTJfYmEucmRhdGEiKQpgYGAKCgpgYGB7cn0KZGF0YTIkcCA8LSAoZGF0YTIkbS9kYXRhMiRzaXplKQpuYW1lcyhkYXRhMikKZ2dwbG90KGRhdGEyLCBtYXBwaW5nID0gYWVzKGNvbCA9IGZhY3RvcihwKSwgeCA9IGJldGEsIHkgPSBlaWdlbnZhbHVlMikpICsKICBnZW9tX3BvaW50KHNpemUgPSAwLjUpICsKICBzdGF0X3Ntb290aChtZXRob2QgPSAnbG0nKSArCiAgc2NhbGVfc2l6ZV9jb250aW51b3VzKHJhbmdlID0gYygwLjEsMSkpICsKICBsYWJzKHggPSAiQmV0YSIsIHkgPSBUZVgoIlNlY29uZCBFaWdlbnZhbHVlIiksIHRpdGxlID0gVGVYKCJTZWNvbmQgRWlnZW52YWx1ZSBnaXZlbiBNYXRyaXggRGVuc2l0eSIpICkgKwogIGd1aWRlcyhjb2wgPSBndWlkZV9sZWdlbmQoIkxpbmsgRGVuc2l0eSAoYnkgbS9uKSIpKSAgKwogIHRoZW1lX2J3KCkKYGBgCkl0IGFwcGVhcnMgdGhhdCBtL249ZGVuc2l0eSBpcyBpdHMgb3duIGZlYXR1cmUsIGl0IGRvZXMgbm90IGFmZmVjdCBFMiBsaW5lYXJseSBzbyBsZXRzIGhvbGQgYmV0YSBjb25zdGFudCBhbmQgc2VlIGhvdyBpdCBhZmZlY3RzIEUyLgoKSWYgZm9yIGluc3RhbmNlIG0vbiBpbmNyZWFzZXMsIHNheSBxdWFkcmF0aWNhbGx5IGZvciBhIGNvbnN0YW50IGJldGEsCnRoZW4gSSBzaG91bGQgdHJ5IGFuZCBmaXQgYSBsaW5lYXIgbW9kZWwgdG8gKG0vbileMipiZXRhCgpgYGB7cn0KbSAgICA8LSBzZXEoZnJvbSA9IDEsIHRvID0gOSwgbGVuZ3RoLm91dCA9IDIwKQpiZXRhIDwtIHNlcShmcm9tID0gMSwgdG8gPSA2LCBsZW5ndGgub3V0ID0gMTApCmJldGEgPC0gMjUKc3ogPC0gc2VxKGZyb20gPSAxMDAsIHRvID0gMTAwMCwgbGVuZ3RoLm91dCA9IDEwKSAlPiUgcmV2KCkgIyBCaWcgbnVtYmVycyBmaXJzdCAKCmlucHV0X3ZhciA8LSBleHBhbmQuZ3JpZCgibSIgPSBtLCAiYmV0YSIgPSBiZXRhLCAic2l6ZSIgPSBzeikKaW5wdXRfdmFyCgoKcm0oWSwgZGF0YSkKbmMgPC0gbGVuZ3RoKHJhbmRvbV9ncmFwaCgxLCAxLCAxKSkKWSA8LSBtYXRyaXgobmNvbCA9IG5jLCBucm93ID0gbnJvdyhpbnB1dF92YXIpKQpmb3IgKGkgaW4gMTpucm93KGlucHV0X3ZhcikpIHsKICBYIDwtIGFzLnZlY3RvcihpbnB1dF92YXJbaSxdKQogIFlbaSxdIDwtICByYW5kb21fZ3JhcGgoWCRtLCBYJGJldGEsIFgkc2l6ZSkKICBwcmludChpL25yb3coaW5wdXRfdmFyKSkKfQppZiAoc3VtKGFicyhZKSAhPSBhYnMoUmUoWSkpKSA9PSAwKSB7CiAgWSA8LSBSZShZKQp9Cm5yb3coaW5wdXRfdmFyKQpucm93KFkpClkgPC0gYXMuZGF0YS5mcmFtZShZKTsgY29sbmFtZXMoWSkgPC0gYygiZWlnZW52YWx1ZTIiLCAiQV9kZW5zIiwgInRyYWNlIikKKGRhdGEyIDwtIGNiaW5kKGlucHV0X3ZhciwgWSkpICU+JSBoZWFkKCkKYGBgCgoKCmBgYHtyfQpkYXRhMiRwIDwtIChkYXRhMiRtL2RhdGEyJHNpemUpCm5hbWVzKGRhdGEyKQpnZ3Bsb3QoZGF0YTIsIG1hcHBpbmcgPSBhZXMoY29sID0gZmFjdG9yKHNpemUpLCB4ID0gbS9zaXplLCB5ID0gZWlnZW52YWx1ZTIpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMC41KSArCiAgc3RhdF9zbW9vdGgobWV0aG9kID0gJ2xtJykgKwogIHNjYWxlX3NpemVfY29udGludW91cyhyYW5nZSA9IGMoMC4xLDEpKSArCiAgbGFicyh4ID0gIm0vc2l6ZSIsIHkgPSBUZVgoIlNlY29uZCBFaWdlbnZhbHVlIiksIHRpdGxlID0gVGVYKCJTZWNvbmQgRWlnZW52YWx1ZSBnaXZlbiBNYXRyaXggRGVuc2l0eSIpICkgKwogIGd1aWRlcyhjb2wgPSBndWlkZV9sZWdlbmQoIlNpemUiKSkgICsKICB0aGVtZV9idygpCmBgYApTbyB3aGF0IGFib3V0IHdoZW4gSSB2ZXJ5IG0sIGkuZS4gbGV0cyBtYXAgdGhhdCB0byBjb2xvdXIgbm93OgoKYGBge3J9Cm0gPC0gMTo4CmJldGEgPC0gc2VxKGZyb20gPSAxLCB0byA9IDYsIGxlbmd0aC5vdXQgPSAxMCkKYmV0YSA8LSA1CnN6IDwtIHNlcShmcm9tID0gMTAwLCB0byA9IDEwMDAsIGxlbmd0aC5vdXQgPSAyMCkgJT4lIHJldigpICMgQmlnIG51bWJlcnMgZmlyc3QgCgppbnB1dF92YXIgPC0gZXhwYW5kLmdyaWQoIm0iID0gbSwgImJldGEiID0gYmV0YSwgInNpemUiID0gc3opCmlucHV0X3ZhcgoKCnJtKFksIGRhdGEpCm5jIDwtIGxlbmd0aChyYW5kb21fZ3JhcGgoMSwgMSwgMSkpClkgPC0gbWF0cml4KG5jb2wgPSBuYywgbnJvdyA9IG5yb3coaW5wdXRfdmFyKSkKZm9yIChpIGluIDE6bnJvdyhpbnB1dF92YXIpKSB7CiAgWCA8LSBhcy52ZWN0b3IoaW5wdXRfdmFyW2ksXSkKICBZW2ksXSA8LSAgcmFuZG9tX2dyYXBoKFgkbSwgWCRiZXRhLCBYJHNpemUpCiAgcHJpbnQoaS9ucm93KGlucHV0X3ZhcikpCn0KaWYgKHN1bShhYnMoWSkgIT0gYWJzKFJlKFkpKSkgPT0gMCkgewogIFkgPC0gUmUoWSkKfQpucm93KGlucHV0X3ZhcikKbnJvdyhZKQpZIDwtIGFzLmRhdGEuZnJhbWUoWSk7IGNvbG5hbWVzKFkpIDwtIGMoImVpZ2VudmFsdWUyIiwgIkFfZGVucyIsICJ0cmFjZSIpCihkYXRhMiA8LSBjYmluZChpbnB1dF92YXIsIFkpKSAlPiUgaGVhZCgpCgoKCmRhdGEyJHAgPC0gKGRhdGEyJG0vZGF0YTIkc2l6ZSkKbmFtZXMoZGF0YTIpCmdncGxvdChkYXRhMiwgbWFwcGluZyA9IGFlcyhjb2wgPSBmYWN0b3IobSksIHggPSBtL3NpemUsIHkgPSBlaWdlbnZhbHVlMikpICsKICBnZW9tX3BvaW50KHNpemUgPSAwLjUpICsKICBzdGF0X3Ntb290aCgpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxKSkgKwogIGxhYnMoeCA9ICJtL3NpemUiLCB5ID0gVGVYKCJTZWNvbmQgRWlnZW52YWx1ZSIpLCB0aXRsZSA9IFRlWCgiU2Vjb25kIEVpZ2VudmFsdWUgZ2l2ZW4gTWF0cml4IERlbnNpdHkiKSApICsKICBndWlkZXMoY29sID0gZ3VpZGVfbGVnZW5kKCJWZXJ0aWNlcyBBZGRlZFxuIEVhY2ggU3RlcCIpKSAgKwogIHRoZW1lX2J3KCkKYGBgCgoKRXZlbiB0aG91Z2ggaXQncyBoYXJkIHRvIGNhcHR1cmUgdGhlIGJlaGF2aW91ciBvZiBtL24sIHRoZSBzaXplIG9mIHRoZSBncmFwaCBhbmQgdGhlIGF2ZXJhZ2Ugb3V0ZGVncmVlIGFyZSBnb2luZyB0byBiZSBjb25zdGFudHMgYW5kIHNvIHRoaXMgcmVsYXRpb25zaGlwIHNob3VsZCBwZXJzaXN0CmZvciBncmFwaHMgd2hlcmUgbTw8bi4KCgoKYWN0dWFsbHkgaWYgdGhleSBhcmUgYWxsIGxpbmVhcmx5IHJlbGF0ZWQsIG1heWJlIEkgY291bGQgdXNlIGEgbXVsdGlwbGUgbGluZWFyIHJlZ3Jlc3Npb24/CgpgYGB7cn0KbSA8LSAxOjgKYmV0YSA8LSBzZXEoZnJvbSA9IDEsIHRvID0gMjAsIGxlbmd0aC5vdXQgPSAxMDApCnN6IDwtIHNlcShmcm9tID0gMTAwLCB0byA9IDEwMDAsIGxlbmd0aC5vdXQgPSAyMCkgJT4lIHJldigpICMgQmlnIG51bWJlcnMgZmlyc3QgCgppbnB1dF92YXIgPC0gZXhwYW5kLmdyaWQoIm0iID0gbSwgImJldGEiID0gYmV0YSwgInNpemUiID0gc3opCmlucHV0X3ZhcgoKCnJtKFksIGRhdGEpCm5jIDwtIGxlbmd0aChyYW5kb21fZ3JhcGgoMSwgMSwgMSkpClkgPC0gbWF0cml4KG5jb2wgPSBuYywgbnJvdyA9IG5yb3coaW5wdXRfdmFyKSkKZm9yIChpIGluIDE6bnJvdyhpbnB1dF92YXIpKSB7CiAgWCA8LSBhcy52ZWN0b3IoaW5wdXRfdmFyW2ksXSkKICBZW2ksXSA8LSAgcmFuZG9tX2dyYXBoKFgkbSwgWCRiZXRhLCBYJHNpemUpCiAgcHJpbnQoaS9ucm93KGlucHV0X3ZhcikpCn0KaWYgKHN1bShhYnMoWSkgIT0gYWJzKFJlKFkpKSkgPT0gMCkgewogIFkgPC0gUmUoWSkKfQpucm93KGlucHV0X3ZhcikKbnJvdyhZKQpZIDwtIGFzLmRhdGEuZnJhbWUoWSk7IGNvbG5hbWVzKFkpIDwtIGMoImVpZ2VudmFsdWUyIiwgIkFfZGVucyIsICJ0cmFjZSIpCihkYXRhMiA8LSBjYmluZChpbnB1dF92YXIsIFkpKSAlPiUgaGVhZCgpCgoKCgoKCgptb2QgPC0gbG0oZWlnZW52YWx1ZTIgfiBtL3NpemUgKyBzaXplICsgbSArIGJldGEsIGRhdGEyKQpzdW1tYXJ5KG1vZCkKcGxvdChtb2QpCmBgYAoKCgoKCmBgYHtyfQptb2QgPC0gbG0oZWlnZW52YWx1ZTIgfiBtL3NpemUgKyBtICsgc2l6ZSArIGJldGEgLCBkYXRhID0gZGF0YTIpCm1heChkYXRhMiRtL2RhdGEyJHNpemUpCnN1bW1hcnkobW9kKQojIGxheW91dChtYXQgPSBtYXRyaXgoMTo0LCBucm93ID0gMikpCiMgcGxvdChtb2QpCiMgbWVhbihtb2QkcmVzaWR1YWxzKioyKQpoaXN0KG1vZCRyZXNpZHVhbHMsIGJyZWFrcyA9IDIwMCkKYGBgCgoKCkNsZWFybHkgbm9uLW5vcm1hbCByZXNpZHVhbHMgYnV0ICstNSUgaXMgcHJldHR5IGdvb2QgZm9yIGEgdmVyeSBjb21wbGljYXRlZCByZXN1bHQuCgoKCgoKSSB0aGluayBJIGFscmVhZHkgbG9va2VkIGF0IHRoaXMgYnV0IHRoaXMgYWdhaW4gc2hvd3MgdGhlIHJlbGx5IGNsZWFyLCBuZWFyIGxpbmVhciByZWxhdGlvbnNoaXAuCgoKYGBge3J9CmdncGxvdChkYXRhMiwgbWFwcGluZyA9IGFlcyhjb2wgPSBmYWN0b3IobSksIHggPSBiZXRhLCB5ID0gZWlnZW52YWx1ZTIpKSArCiAgZ2VvbV9zbW9vdGgoc2l6ZSA9IDAuNSkgKwojICBzdGF0X3Ntb290aCgpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxKSkgKwogIGxhYnMoeCA9ICJiZXRhIiwgeSA9IFRlWCgiU2Vjb25kIEVpZ2VudmFsdWUiKSwgdGl0bGUgPSBUZVgoIlNlY29uZCBFaWdlbnZhbHVlIGdpdmVuIE1hdHJpeCBEZW5zaXR5IikgKSArCiAgZ3VpZGVzKGNvbCA9IGd1aWRlX2xlZ2VuZCgiVmVydGljZXMgQWRkZWRcbiBFYWNoIFN0ZXAiKSkgICsKICB0aGVtZV9idygpCmBgYAoKT2J2aW91c2x5IHdlIGNhbid0IGtub3cgbSwgYnV0LCB3ZSBjYW4ga25vdyB0aGUgYXZlcmFnZSBvdXQgZGVncmVlLCBzbyBsZXQncywKdGFrZSBhIGdyYXBoLAptZWFzdXJlIHRoZSBhdmVyYWdlIG91dCBkZWdyZWUsCnVzZSBvdXIgbW9kZWwsCm1lYXN1cmUgaXQncyBwZXJmb3JtYW5jZS4KCgoKYGBge3J9CgpgYGAKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoK